1054D - Changing Array - CodeForces Solution

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <unordered_map>
#include <climits>
#include <unordered_set>

using namespace std;

typedef long long LL;

class CF1054D {
public:
    LL solve(const vector<int> &a, int k) {
        LL n = a.size();
        unordered_map<int, int> xor2cnt;
        int mask = (1 << k) - 1;

        xor2cnt[0]++;
        for (int i = 0, xorSum = 0; i < n; i++) {
            xorSum ^= a[i];
            int newXorSum = min(xorSum, xorSum ^ mask);
            xor2cnt[newXorSum]++;
        }
        LL ans = (1 + n) * n / 2;
        for (auto &ite : xor2cnt) {
            ans -= calcZero(ite.second);
        }
        return ans;
    }
    LL calcZero(LL cnt) {
        LL x = cnt / 2;
        LL y = cnt - x;
        return x * (x - 1) / 2 + y * (y - 1) / 2;
    }
};

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    printf("%lld\n", CF1054D().solve(a, k));
    return 0;
}